// 节点结构
class Node {
  constructor (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
  show () {
    return this.data
  }
}

class BST {
  constructor () {
    this.root = null
  }
  // 插入一个节点
  insertNode (data) {
    // 创建节点
    let node = new Node(data, null, null)
    // 若没有根节点，则初始化根节点
    if (this.root === null) {
      this.root = node
    } else {
      let current = this.root
      let parent
      while (true) {
        parent = current
        // 如果数据小于当前节点，那么该节点一定在left分支
        if (data < current.data) {
          // 获取当前节点的左节点数据与要插入的数据进行对比
          current = current.left
          // 如果当前节点的做节点为空，那么直接插入节点到该节点上并跳出循环
          if (current === null) {
            parent.left = node
            break
          }
        } else { // 如果数据大于当前节点，那么该节点一定在right分支
          current = current.right
          if (current === null) {
            parent.right = node
            break
          }
        }
      }
    }
  }
  // 插入多个节点
  insert (treeArr) {
    treeArr.forEach(node => {
      this.insertNode(node)
    });
  }
  // 先序遍历
  preOrder (node) {
    if (node) {
      console.log(node.show() + "");
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }
  // 中序
  inOrder(node) {
    if (node) {
      this.inOrder(node.left);
      console.log(node.show() + "");
      this.inOrder(node.right);
    }
  }
  // 后序
  postOrder (node) {
    if(node){
      this.postOrder( node.left );
      this.postOrder( node.right );
      console.log(node.show() + "");
    }
  }
  // 查找最小值
  getMin() {
    let current = this.root;
    while (current.left){
      current = current.left;
    }
    return current.show();
  }
  // 查找最小值
  getSmallest(node) {
    if (node.left == null) {
      return node;
    }
    else {
      return this.getSmallest(node.left);
    }
  }
  // 查找最大值
  getMax () {
    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.show();
  }
  // 查找给定值
  find (data) {
    let current = this.root;
    while (current){
      if(current.data == data){
        return current;
      } else if(current.data < data){
        current = current.right;
      } else{
        current = current.left;
      }
    }
    return null;
  }
}

let bstTree = new BST()

bstTree.insert([20, 1, 19, 21])
bstTree.preOrder(bstTree.root)
bstTree.inOrder(bstTree.root)
bstTree.postOrder(bstTree.root)
let maxNode = bstTree.getMax()
console.log("maxNode====>", maxNode);

let seachNode = bstTree.find(20)
console.log("seachNode====>", seachNode);

let minNode = bstTree.getSmallest(bstTree.root)
console.log("mini====>", minNode);
// console.log(bstTree.root, 'bstTree');